import java.awt.*;
import java.util.Arrays;

/**
 * 自底向上
 */
public class AlgoVisualizer2 {

    private MergeSortData data;
    private AlgoFrame frame;
    private static int DELAY = 20;

    public AlgoVisualizer2(int sceneWidth, int sceneHeight, int N) {
        // 初始化数据
        data = new MergeSortData(N, sceneHeight);

        EventQueue.invokeLater(() -> {
            frame = new AlgoFrame("Merge Sort Visualization", sceneWidth, sceneHeight);

            // https://docs.oracle.com/javase/tutorial/uiswing/concurrency/dispatch.html
            // Tasks on the event dispatch thread must finish quickly; if they don't, unhandled events back up and the user interface becomes unresponsive.
            new Thread(this::run).start();
        });
    }

    // 动画逻辑
    private void run() {
        setData(-1, -1, -1);

        for (int sz = 1; sz < data.numbers.length; sz *= 2) {
            for (int i = 0; i < data.numbers.length - 1; i += sz + sz) {
                merge(i, i + sz - 1, Math.min(i + sz + sz - 1, data.numbers.length - 1));
            }
        }

        setData(0, data.numbers.length - 1, data.numbers.length - 1);
    }

    private void merge(int l, int mid, int r) {
        int[] aux = Arrays.copyOfRange(data.numbers, l, r + 1);

        int i = l, j = mid + 1;
        for (int k = l; k <= r; k ++) {
            if (i > mid) {
                data.numbers[k] = aux[j - l];
                j ++;
            } else if (j > r) {
                data.numbers[k] = aux[i - l];
                i ++;
            } else if (aux[i - l] < aux[j - l]) {
                data.numbers[k] = aux[i - l];
                i ++;
            } else {
                data.numbers[k] = aux[j - l];
                j ++;
            }

            setData(l, r, k);
        }
    }

    private void setData(int l, int r, int mergeIndex) {
        data.l = l;
        data.r = r;
        data.mergeIndex = mergeIndex;

        frame.render(data);
        AlgoVisHelper.pause(DELAY);
    }

    public static void main(String[] args) {
        int sceneWidth = 800;
        int sceneHeight = 800;
        int N = 100;

        AlgoVisualizer2 visualizer = new AlgoVisualizer2(sceneWidth, sceneHeight, N);
    }
}
